package com.jz.algorithm.String;


import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * @Classname StringSeries
 * @Description String系列LeetCode题目
 * @Date 2021/10/20 14:42
 * @Author Jz
 * @Version
 */
public class StringSeries {

    /**
     * @Methodname backspaceCompare leetcode 844
     * @Description 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
     * 如果相等，返回 true ；否则，返回 false 。
     * @Date 2021/10/20 16:20
     * @Author Jz
     * @Return
     * @Param
     * @Example 输入：s = "ab#c", t = "ad#c"  输出：true解释：S 和 T 都会变成 “ac”。
     */
    public  boolean backspaceCompare(String s,String t){
     return    getString(s).equals(getString(t));

    }

    public static String getString(String s) {
        char[] chars = s.toCharArray();
        int count=0;
        StringBuilder stringBuilder=new StringBuilder();

        for (int length = chars.length-1; length >= 0; length--) {
            if (chars[length]=='#'){
                count++;
            }
            else {
                if (count>0){
                    count--;

                }
                else {
                    stringBuilder.append(chars[length]);
                }
            }
        }
        return stringBuilder.toString();
    }

    /**
     * @Methodname getHint leetcode 299
     * @Description 写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：
     *
     * 猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls", 公牛），
     * 有多少位属于数字猜对了但是位置不对（称为 "Cows", 奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。
     * 给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。
     *
     * 提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。
     *
     * 请注意秘密数字和朋友猜测的数字都可能含有重复数字
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/bulls-and-cows
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @Date 2021/11/8 9:43
     * @Author Jz
     * @Return
     * @Param
     */
    public static String getHint(String secret, String guess) {

        int [] cnt1 = new int[10], cnt2 = new int[10];


        int x=0;
        int y=0;


        for (int i = 0; i < secret.length(); i++) {
            int c1 = secret.charAt(i) - '0', c2= guess.charAt(i) - '0';
            if (c1==c2){
                x++;
                continue;
            }else {
               cnt1[c1]++;
              cnt2[c2]++;

            }






        }
        for (int i1 = 0; i1 < 10; i1++) {
            y+=Math.min(cnt1[i1],cnt2[i1]);
        }
        return x+"A"+y+"B";


    }


    /**
     * @Methodname reverseString
     * @Description 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     *
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题
     * @Date 2021/11/15 14:35
     * @Author Jz
     * @Return null
     * @Param 字符数组s
     */
    public static void reverseString(char[] s) {
       int p=0;
       int q=s.length-1;
       while(p<q){
           char temp=s[p];
           s[p]=s[q];
           s[q]=temp;
           p++;
           q--;
       }


    }
    public static void reverseString(char[] s,int p,int q) {

        while(p<q){
            char temp=s[p];
            s[p]=s[q];
            s[q]=temp;
            p++;
            q--;
        }


    }
    /**
     * @Methodname replaceSpace
     * @Description 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
     * @Date 2021/11/16 9:54
     * @Author Jz
     * @Return 替换后的字符串
     * @Param 原来的字符串
     */
    public static String replaceSpace(String s) {

        char[] chars = s.toCharArray();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < chars.length; i++) {
            if ( chars[i]==' '){
                stringBuilder.append("%20");
            }else {
                stringBuilder.append(chars[i]);
            }
        }
        return  stringBuilder.toString();
    }

        public static String reverseStr(String s, int k) {
            char[] arr = s.toCharArray();

            for(int i = 0; i< arr.length; i+=2*k){
                reverseString(arr, i, Math.min(i + k, arr.length) - 1);
            }
            return new String(arr);



    }
    
    /**
     * @Methodname reverseWords
     * @Description 给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
     *
     * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
     *
     * 请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/reverse-words-in-a-string
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @Date 2021/11/16 10:29
     * @Author Jz
     * @Return 
     * @Param 
     */
    public static String reverseWords(String s) {
        s=s.trim();
        String [] strings=new String[s.length()];
        int index=0;
        int start =0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)==' '|| i==s.length()-1) {
                if (!s.substring(start, i + 1).equals(" ")) {
                    strings[index++] = s.substring(start, i + 1);
                }
                start=i+1;
            }
        }

        int p=0;
        int q=index-1;
        while (p<q){
            if (p==0) {
                String temp = strings[p];
                strings[p] = strings[q].trim()+" ";
                strings[q] = temp.trim();
                p++;
                q--;
            }
            else {
                String temp = strings[p];
                strings[p] = strings[q].trim()+" ";
                strings[q] = temp.trim()+" ";
                p++;
                q--;

            }

        }
        StringBuilder stringBuilder=new StringBuilder();
        for (String string : strings) {
            if (string!=null){
            stringBuilder.append(string);
        }
        }
        return stringBuilder.toString();
    }
    public  static  String reverseWords1(String s){

        // 先去除掉多余的空格

        String s1 = removeSpace(s);

        // 翻转字符串
       String s2=reverseAllWords(s1,0,s1.length()-1);
    String s3= reverseEachWord(s2);
        System.out.println(s3);
        System.out.println(s2);

       //

        return "";

    }

    private static String reverseEachWord(String s2) {
        int n=0;
        int start=0;
        StringBuilder stringBuilder=new StringBuilder();
        while (n<=s2.length()){
            if (s2.charAt(n)==' ' || n==s2.length()){
                String s = reverseAllWords(s2, start, n);
                stringBuilder.append(s);
                start=n;
            }
            n++;

        }
        return  stringBuilder.toString();
    }

    private static String reverseAllWords(String s1,int p,int q) {

        char[] chars = s1.toCharArray();

        while (p<q){
         char temp=chars[p];
         chars[p]=chars[q];
         chars[q]=temp;
         p++;
         q--;
        }
        return  new String(chars);
    }

    public static String removeSpace(String s){
        s=s.trim();
        char[] chars = s.toCharArray();
        int p=0;
        int q=0;
        for (; p < chars.length; p++) {

           if (p-1>0 &&s.charAt(p)==' '&& s.charAt(p-1)==' '){
               continue;
           }
           else {
               chars[q++]=chars[p];

           }




        }

        return  new String(chars).substring(0,q);



    }

    /**
     * @Methodname reverseLeftWords
     * @Description 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
     *
     *  
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @Date 2021/11/16 16:18
     * @Author Jz
     * @Return 
     * @Param 
     */
    public String reverseLeftWords(String s, int n) {
        String substring = s.substring(0, n + 1);
        String substring1 = s.substring(n + 1);
        return  substring1+substring;

    }


    
    /**
     * @Methodname strStr
     * @Description 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。kmp 算法
     * @Date 2021-11-19 10:26
     * @Author Jz
     * @Return 
     * @Param 
     */
    public int strStr(String haystack, String needle) {

        //两种特殊情况
        if (needle.length() == 0) {
            return 0;
        }
        if (haystack.length() == 0) {
            return -1;
        }
        // char 数组
        char[] hasyarr = haystack.toCharArray();
        char[] nearr = needle.toCharArray();
        //长度
        int halen = hasyarr.length;
        int nelen = nearr.length;
        //返回下标
        return kmp(hasyarr,halen,nearr,nelen);

    }
    public int kmp (char[] hasyarr, int halen, char[] nearr, int nelen) {
        //获取next 数组
        int[] next = next(nearr,nelen);
        int j = 0;
        for (int i = 0; i < halen; ++i) {
            //发现不匹配的字符，然后根据 next 数组移动指针，移动到最大公共前后缀的，
            //前缀的后一位,和咱们移动模式串的含义相同
            while (j > 0 && hasyarr[i] != nearr[j]) {
                j = next[j - 1] + 1;
                //超出长度时，可以直接返回不存在
                if (nelen - j + i > halen) {
                    return -1;
                }
            }
            //如果相同就将指针同时后移一下，比较下个字符
            if (hasyarr[i] == nearr[j]) {
                ++j;
            }
            //遍历完整个模式串，返回模式串的起点下标
            if (j == nelen) {
                return i - nelen + 1;
            }
        }
        return -1;
    }
    /**
     * @Methodname next
     * @Description 获取next数组，next数组存放的就是当前最长公共前后缀的长度
     * @Date 2021-11-19 13:24
     * @Author Jz
     * @Return next 数组
     * @Param
     */
    public static   int[] next (char[] needle,int len) {
        //定义 next 数组
        int[] next = new int[len];
        // 初始化
        next[0] = -1;
        int k = -1;
        for (int i = 1; i < len; ++i) {
            //我们此时知道了 [0,i-1]的最长前后缀，但是k+1的指向的值和i不相同时，我们则需要回溯
            //因为 next[k]就时用来记录子串的最长公共前后缀的尾坐标（即长度）
            //就要找 k+1前一个元素在next数组里的值,即next[k+1]
            while (k != -1 && needle[k + 1] != needle[i]) {
                k = next[k];
            }
            // 相同情况，就是 k的下一位，和 i 相同时，此时我们已经知道 [0,i-1]的最长前后缀
            //然后 k - 1 又和 i 相同，最长前后缀加1，即可
            if (needle[k+1] == needle[i]) {
                ++k;
            }
            next[i] = k;

        }
        return next;
    }

    

    public static void main(String[] args) {

     //   String s = reverseWords1("  Bob    Loves  Alice   ");
        char [] chars={'a','a','b'};
        for (int i : next(chars, chars.length)) {
            System.out.println(i);
        }
//        System.out.println(reverseStr("abcdefg", 2));

    }




    /**
     * @Methodname findMinStep
     * @Description 你正在参与祖玛游戏的一个变种。
     *
     * 在这个祖玛游戏变体中，桌面上有 一排 彩球，每个球的颜色可能是：红色 'R'、黄色 'Y'、蓝色 'B'、绿色 'G' 或白色 'W' 。你的手中也有一些彩球。
     *
     * 你的目标是 清空 桌面上所有的球。每一回合：
     *
     * 从你手上的彩球中选出 任意一颗 ，然后将其插入桌面上那一排球中：两球之间或这一排球的任一端。
     * 接着，如果有出现 三个或者三个以上 且 颜色相同 的球相连的话，就把它们移除掉。
     * 如果这种移除操作同样导致出现三个或者三个以上且颜色相同的球相连，则可以继续移除这些球，直到不再满足移除条件。
     * 如果桌面上所有球都被移除，则认为你赢得本场游戏。
     * 重复这个过程，直到你赢了游戏或者手中没有更多的球。
     * 给你一个字符串 board ，表示桌面上最开始的那排球。另给你一个字符串 hand ，表示手里的彩球。请你按上述操作步骤移除掉桌上所有球，计算并返回所需的 最少 球数。如果不能移除桌上所有的球，返回 -1
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/zuma-game
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @Date 2021/11/9 9:42
     * @Author Jz
     * @Return 最小步数
     * @Param board 一排彩球 ，hand 你手上的彩球
     */
    public int findMinStep(String board, String hand) {

        int count=0;
        int p=0;
        int n=1;

        //先找出是连续同样元素的的起始下标

       int [] i=getLastPosition(board);




       return 0;


    }

    private int[] getLastPosition(String board) {
      int [] a= new int[2];
        int p=0;
        int q=1;
        int start=-1;
        int end=-1;
        while(q<board.length()){
            while (board.charAt(p)==board.charAt(q)){
                start=p;
                p+=2;
                q+=2;
            }
            if (start!=-1){
                end=q;
            }
            p+=1;
            q+=1;

        }
        a[0]=start;
        a[1]=end;
        return a;
    }



    /**
     * @Methodname repeatedSubstringPattern
     * @Description 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
     * @Date 2021-11-24 14:41
     * @Author Jz
     * @Return 是否可以
     * @Param 字符串
     */
    public boolean repeatedSubstringPattern(String s) {

        if(s.length()==0){
            return false;
        }
        char[] nearr = s.toCharArray();

        int [] next=next(nearr);
        for( int i=2;i<next.length;i++){
            if(nearr.length%next[i]==0){
                return true;
            }
        }
        return false;

    }
    public int [] next(char [] nearr){

        int [] next=new int[nearr.length];
        int k=-1;
        for(int i=1;i< nearr.length;++i){

            while(k!=-1 &&nearr[k+1]!=nearr[i]){
                k=next[k];
            }
            if(nearr[k+1]==nearr[i]){
                ++k;
            }
            next[i]=k;

        }
        return next;
    }




}
